package com.hdu.hot100.graph;

import java.util.Arrays;


public class lc208 {
    class Trie {

        static int N = 100000;

        static final int[][] TREE = new int[N][26];
        static final int[] PASS = new int[N];
        static final int[] END = new int[N];
        static int CNT = 1;

        public Trie() {
            for (int i = 0; i < N; i++)
            {
                Arrays.fill(TREE[i], 0);
                PASS[i] = 0;
                END[i] = 0;
            }
            CNT = 1;
        }

        public void insert(String word) {
            int cur = 1;
            for (int i = 0; i < word.length(); i++)
            {
                int u = word.charAt(i) - 'a';
                if (TREE[cur][u] == 0)
                {
                    TREE[cur][u] = ++CNT;
                }
                cur = TREE[cur][u];
                PASS[cur]++;
            }
            END[cur]++;
        }

        public boolean search(String word) {
            int cur = 1;
            for (int i = 0; i < word.length(); i++)
            {
                int u = word.charAt(i) - 'a';
                if (TREE[cur][u] == 0)
                {
                    return false;
                }
                cur = TREE[cur][u];
            }
            return END[cur] > 0;
        }

        public boolean startsWith(String prefix) {
            int cur = 1;
            for (int i = 0; i < prefix.length(); i++)
            {
                int u = prefix.charAt(i) - 'a';
                if (TREE[cur][u] == 0)
                {
                    return false;
                }
                cur = TREE[cur][u];
            }
            return PASS[cur] > 0;
        }
    }

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

}
